Search results for "grover's algorithm"
showing 7 items of 7 documents
Span programs for functions with constant-sized 1-certificates
2012
Besides the Hidden Subgroup Problem, the second large class of quantum speed-ups is for functions with constant-sized 1-certificates. This includes the OR function, solvable by the Grover algorithm, the element distinctness, the triangle and other problems. The usual way to solve them is by quantum walk on the Johnson graph. We propose a solution for the same problems using span programs. The span program is a computational model equivalent to the quantum query algorithm in its strength, and yet very different in its outfit. We prove the power of our approach by designing a quantum algorithm for the triangle problem with query complexity O(n35/27) that is better than O(n13/10) of the best p…
Grover’s Algorithm with Errors
2013
Grover’s algorithm is a quantum search algorithm solving the unstructured search problem of size n in \(O(\sqrt{n})\) queries, while any classical algorithm needs O(n) queries [3].
Correcting for Potential Barriers in Quantum Walk Search
2015
A randomly walking quantum particle searches in Grover's $\Theta(\sqrt{N})$ iterations for a marked vertex on the complete graph of $N$ vertices by repeatedly querying an oracle that flips the amplitude at the marked vertex, scattering by a "coin" flip, and hopping. Physically, however, potential energy barriers can hinder the hop and cause the search to fail, even when the amplitude of not hopping decreases with $N$. We correct for these errors by interpreting the quantum walk search as an amplitude amplification algorithm and modifying the phases applied by the coin flip and oracle such that the amplification recovers the $\Theta(\sqrt{N})$ runtime.
Nonadiabatic quantum search algorithms
2007
7 pages, 4 figures.-- PACS nrs.: 03.67.Lx, 05.45.Mt, 72.15.Rn.-- ISI Article Identifier: 000251326400049.-- ArXiv pre-print available at: http://arxiv.org/abs/0706.1139
Grover’s Search with Faults on Some Marked Elements
2016
Grover's algorithm is a quantum query algorithm solving the unstructured search problem of size N using $$O\sqrt{N}$$ queries. It provides a significant speed-up over any classical algorithm [2]. The running time of the algorithm, however, is very sensitive to errors in queries. Multiple authors have analysed the algorithm using different models of query errors and showed the loss of quantum speed-up [1, 4]. We study the behavior of Grover's algorithm in the model where the search space contains both faulty and non-faulty marked elements. We show that in this setting it is indeed possible to find one of marked elements in $$O\sqrt{N}$$ queries.
An improved quantum query algorithm for computing AND Boolean function
2010
We consider the quantum query model for computing Boolean functions. The definition of the function is known, but a black box contains the input X = (x 1 , x 2 , …, x n ). Black box can be accessed by querying x i values. The goal is to develop an algorithm, which would compute the function value for arbitrary input using as few queries to the black box as possible. We present two different quantum query algorithms for computing the basic Boolean function — logical AND of two bits. Both algorithms use only one query to determine the function value. Correct answer probability for the first algorithm is 80%, but for the second algorithm it is 90%. To compute this function with the same probab…
From a causal representation of multiloop scattering amplitudes to quantum computing in the Loop-Tree Duality
2023
La teoría cúantica de campos con enfoque perturbativo ha logrado de manera exitosa proporcionar predicciones teóricas increíblemente precisas en física de altas energías. A pesar del desarrollo de diversas técnicas con el objetivo de incrementar la eficiencia de estos cálculos, algunos ingredientes continuan siendo un verdadero reto. Este es el caso de las amplitudes de dispersión con lazos múltiples, las cuales describen las fluctuaciones cuánticas en los procesos de dispersión a altas energías. La Dualidad Lazo-Árbol (LTD) es un método innovador, propuesto con el objetivo de afrontar estas dificultades abriendo las amplitudes de lazo a amplitudes conectadas de tipo árbol. En esta tesis pr…